﻿
 public class TreeNode {
     public int val;
     public TreeNode left;
     public TreeNode right;
     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
 }
 
public class Solution {
    public IList<int> PreorderTraversal(TreeNode root)
    {
        List<int> resList = new List<int>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (root is not null) stack.Push(root);

        TreeNode node;
        while (stack.Count != 0)
        {
            node = stack.Peek();
            if (node is not null)
            {
                stack.Pop();
                if (node.right is not null) stack.Push(node.right);
                if (node.left is not null) stack.Push(node.left);
                
                stack.Push(node);
                stack.Push(null);
            }
            else
            {
                stack.Pop();
                node = stack.Pop();
                resList.Add(node.val);
            }
        }
        return resList;
    }

    public static void Main(string[] args)
    {
        int?[] root = [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9];
        TreeNode rootNode = CreateTree(root); // 创建二叉树

        Solution solution = new Solution();
        
        IList<int> resList = solution.PreorderTraversal(rootNode);

        foreach (int r in resList)
        {
            Console.Write($"{r} ");
        }
    }

    private static TreeNode CreateTree(int?[] root)
    {
        if (root.Length == 0 || root[0] is null)
        {
            return null;
        }

        Queue<TreeNode> queue = new Queue<TreeNode>();
        TreeNode rootNode = new TreeNode(root[0].Value);
        queue.Enqueue(rootNode);
        int i = 1;
        TreeNode node;
        while (queue.Count != 0 && i < root.Length)
        {
            node = queue.Dequeue();
            if (root[i] is not null)
            {
                node.left = new TreeNode(root[i].Value);
                queue.Enqueue(node.left);
            }

            i++;
            if (i >= root.Length) break;
            if (root[i] is not null)
            {
                node.right = new TreeNode(root[i].Value);
                queue.Enqueue(node.right);
            }

            i++;
        }

        return rootNode;
    }
}